package PriorityQueue;

import java.util.Arrays;
import java.util.PriorityQueue;

public class MyPrioQueue {
    public int[] elem;
    public int UsedSize;

    public MyPrioQueue() {
        this.elem = new int[10];
    }

    public void itElem(int[] Array) {
        for (int i = 0; i < Array.length; i++) {
            elem[i] = Array[i];
            UsedSize++;
        }
    }

    // 大根堆的创建
    public void createBigHeap() {
        for (int parent = (UsedSize - 1 - 1) / 2; parent >= 0; parent--) {
            siftDown(parent, UsedSize);
        }
    }

    // 向下调整
    public void siftDown(int parent, int end) {
        int child = 2 * parent + 1;
        while (child < end) {
            if (elem[child] < elem[child + 1] && child + 1 < UsedSize) {
                child++;
            }
            if (elem[child] > elem[parent]) {
                swap(child, parent);
                parent = child;
                child = 2 * parent + 1;
            } else {
                break;
            }
        }
    }

    public void swap(int i, int j) {
        int temp = elem[i];
        elem[i] = elem[j];
        elem[j] = temp;
    }

    public int pop() {
        int tmp = elem[0];
        swap(0, UsedSize - 1);
        siftDown(0, UsedSize);
        UsedSize--;
        return tmp;
    }

    public int peek() {
        return elem[0];
    }

    public void offer(int val) {
        if (isFull()) {
            this.elem = Arrays.copyOf(elem, 2 * elem.length);
        }
        elem[UsedSize] = val;
        UsedSize++;
        siftUp(UsedSize - 1);
    }

    // 向上调整
    public void siftUp(int child) {
        int parent = (child - 1) / 2;
        while (child > 0) {
            if (elem[child] > elem[parent]) {
                swap(child, parent);
                child = parent;
                parent = (child - 1) / 2;
            } else {
                break;
            }
        }
    }

    public boolean isFull() {
        return elem.length == UsedSize;
    }

    public int[] smallestK(int[] arr, int k) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        for (int i = 0; i < arr.length; i++) {
            priorityQueue.offer(arr[i]);
        }
        int[] tmp = new int[k];
        for (int j = 0; j < k; j++) {
            tmp[j] = priorityQueue.poll();
        }
        return tmp;
    }

    public int[] smallestK1(int[] arr, int k) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new Imp());
        int[] tmp = new int[k];
        if (k == 0) {
            return tmp;
        }
        for (int i = 0; i < k; i++) {
            priorityQueue.offer(arr[i]);
        }

        for (int j = k; j < arr.length; j++) {
            int s = priorityQueue.peek();
            if (s > arr[j]) {
                priorityQueue.poll();
                priorityQueue.offer(arr[j]);
            }
        }

        for (int i = 0; i < k; i++) {
            tmp[i] = priorityQueue.poll();
        }
        return tmp;
    }

    // 堆排序
    public void HeapSort() {
        int end = UsedSize - 1;
        while (end > 0) {
            swap(0, end);
            siftDown(0,end-1);
            end--;
        }
    }
}
